package util;

/**
 * @author Egor Kulikov (kulikov@devexperts.com)
 */
class StringUtil {
	public static int[] zAlgorithm(String s) {
		int length = s.length();
		int[] z = new int[length];
		z[0] = 0;

		int left = 0, right = 0;
		for (int i = 1; i < length; i++) {
			if (i > right) {
				int j;
				for (j = 0; i + j < length && s.charAt(i + j) == s.charAt(j); j++);
				z[i] = j;
				left = i;
				right = i + j - 1;
			} else if (z[i - left] < right - i + 1)
				z[i] = z[i - left];
			else {
				int j;
				for (j = 1; right + j < length && s.charAt(right + j) == s.charAt(right - i + j); j++);
				z[i] = right - i + j;
				left = i;
				right = right + j - 1;
			}
		}
		return z;
	}

	public static int indexOf(String s, String sample) {
		int[] z = zAlgorithm(sample + s);
		for (int i = sample.length(); i < z.length; i++) {
			if (z[i] >= sample.length())
				return i - sample.length();
		}
		return -1;
	}

	public static int minimalRotation(String s) {
		int currentStart = 0;
		int nextStart = 1;
		int currentIndex = 1;
		int currentLength = 1;
		while (nextStart + currentIndex <= s.length() * 2) {
			char currentStartChar = s.charAt((currentStart + currentIndex - 1) % s.length());
			char nextStartChar = s.charAt((nextStart + currentIndex - 1) % s.length());
			if (currentStartChar > nextStartChar) {
				currentStart = nextStart++;
				currentIndex = currentLength = 1;
			} else if (currentStartChar < nextStartChar) {
				nextStart += currentIndex;
				currentIndex = 1;
				currentLength = nextStart - currentStart;
			} else if (currentStartChar == nextStartChar && currentIndex < currentLength) {
				currentIndex++;
			} else {
				nextStart += currentLength;
				currentIndex = 1;
			}
		}
		return currentStart;
	}
}
